package arbres;

import listes.Liste;

public interface Binarbre<E extends Comparable<E>> {
	// Un arbre Binarbre<E> est un arbre DE RECHERCHE dont les noeuds ont 0, 1 ou 2 fils.
	// Les 2 fils d'un noeud sont traditionnellement désignés par "fils gauche" et "fils droit".
	// Lorsqu'un noeud est fils unique, il a quand même une position par raport à son père (à gauche ou à droite).
	// RAPPEL : les éléments d'un arbre de recherche sont totalement ordonnables et ne
	// peuvent apparaître qu'en UNE SEULE occurrence.
	
	public E getVal(); // renvoie la valeur de la RACINE de l'arbre
	public boolean isLeaf(); // renvoie vrai si l'arbre est une feuille (racine sans enfants)
	public int familySize(); // renvoie le nombre de DESCENDANTS depuis la RACINE (racine exclue)
	public int height(); // renvoie la hauteur de l'arbre, à partir de la RACINE
	public int balance(); // renvoie le facteur d'équilibrage
	public Binarbre<E> father(); // renvoie le père de l'arbre s'il existe, ou null s'il n'existe pas
	public Binarbre<E> ancestor(); // renvoie le premier ancêtre de l'arbre
	public Binarbre<E> getLeft(); // renvoie le fils gauche s'il existe, ou null s'il n'existe pas
	public Binarbre<E> getRight(); // renvoie le fils droit s'il existe, ou null s'il n'existe pas
	public Binarbre<E> brother(); // renvoie le frère de l'arbre s'il existe, ou null s'il n'existe pas
	public Liste<? extends Binarbre<E>> ancestors(); // renvoie la liste des aieux de l'arbre
	public Liste<? extends Binarbre<E>> gen(int n); // renvoie la liste des déscendants de la racine à la n^ème génération.
		// génération 1 : enfants ; génération 2 : petits enfants ; ...
		// quand l'indice ne correspond pas à une génération possible ou existante, la liste est vide.
	public boolean containsVal(E e); // renvoie vrai si e est contenu dans l'arbre
	public boolean containsAll(Liste<? extends E> liste); // renvoie vrai si tous les éléments de l apparaissent dans l'arbre
	public E maxVal(); // renvoie la valeur maximum
	public E minVal(); // renvoie la valeur minimum
	public Binarbre<E> addVal(E e); // insère e dans l'arbre ; renvoie l'instance courante
	public Binarbre<E> addAll(E... l); // insère tous les éléments de l ; renvoie l'instance courante
	public Binarbre<E> addAll(Liste<E> l); // insère tous les éléments de l ; renvoie l'instance courante
	public Binarbre<E> cutVal(E e); 
		// supprimme e dans l'arbre ;
		// renvoie l'instance courante mise à jour si la racine n'est pas supprimée ;
		// renvoie la fusion des fils si la racine est supprimée (peut être null)
	public Binarbre<E> cutAll(E... l);
		// supprime tous les éléments de l ;
		// renvoie l'instance courante mise à jour si la racine n'est pas supprimée ;
		// renvoie la fusion des fils (MIS A JOUR) si la racine est supprimée (peut être null)
	public Binarbre<E> cutAll(Liste<E> l);
		// idem...
	public Liste<E> prefixe(); // renvoie la liste des éléments stockés dans l'arbre		
		// dans l'ordre correspondant à son parcours préfixe
	public Liste<E> infixe(); // renvoie la liste des éléments stockés dans l'arbre
		// dans l'ordre correspondant à son parcours infixe
	public Liste<E> postfixe(); // renvoie la liste des éléments stockés dans l'arbre
		// dans l'ordre correspondant à son parcours postfixe
	public Liste<E> largeur(); // renvoie la liste des éléments stockés dans l'arbre
		// niveau par niveau à partir de la racine
	public Binarbre<E> equilibre(); // équilibre l'arbre ; renvoie l'instance courante
}
